'lintcode 具有K个不同字符的子串'

Posted on | In

描述

给定字符串S和整数K.
计算长度为K且包含K个不同字符的子串数

样例

String: “abcabc”
K: 3

Answer: 3
substrings: [“abc”, “bca”, “cab”]
String: “abacab”
K: 3

Answer: 2
substrings: [“bac”, “cab”]

思考

维护一个数组temp和一个值cnt，记录当前迭代值i之前k个长度的子串中包含的每个不同字符的个数和个数和。如果cnt==k，是符合要求的子串。每次i向后移动时，都要对第i-K个字符的数量和cnt进行更新。把得到的子串放到set中，最后返回set的大小。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    /**
     * @param stringIn: The original string.
     * @param K: The length of substrings.
     * @return: return the count of substring of length K and exactly K distinct characters.
     */
    int KSubstring(string &stringIn, int K) {
        // Write your code here
        if (stringIn.length() < K)
            return 0;
        set<string> res;
        int cnt = 0;
        vector<int> temp(256,0);
        for (int i = 0; i < stringIn.length();i++) {
            temp[stringIn[i]]++;
            if (temp[stringIn[i]] == 1)
                cnt++;
            if (i >= K) {
                if (temp[stringIn[i-K]] == 1)
                    cnt--;
                temp[stringIn[i-K]]--;
            }
            if (cnt == K)
                res.insert(stringIn.substr(i-K+1,K));
        }
        return res.size();
    }
};
-------------end of filethanks for reading-------------